/*
 * @lc app=leetcode.cn id=560 lang=cpp
 *
 * [560] 和为K的子数组
 */

// @lc code=start
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        //利用哈希表存储前缀和
        //从前往后遍历数组的时候，计算当前sum, 
        //统计sum-k是否出现过，ans += hash[sum - k]
        //并且记录当前的sum值, hash[sum]++
        unordered_map<int, int> hash;
        //需要特别注意sum = 0时，出现过1次，以此进行初始化
        hash[0] = 1;
        int sum = 0;
        int ans = 0;
        for(auto x : nums){
            sum += x;
            ans += hash[sum - k]; //之前有没有出现过sum-k这个前缀和
            hash[sum] ++;
        }
        return ans;
    }
};
// @lc code=end

